AtCoder Beginner Contest 346 A-G 题解

AtCoder Beginner Contest 346

A - Adjacent Product

Question

给你 $N$ 个整数 $A_1,A_2,\cdots ,A_N$ 。同时，定义 $B_i=A_i\times A_{i+1}(1\le i\le N-1)$

按此顺序打印 $B_1,B_2,\cdots ,B_{N-1}$

Solution

按照题意模拟

Code

#include<bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i < n; i++)
        cout << a[i] * a[i + 1] << " ";
    return 0;
}

B - Piano

Question

有一个无限长的钢琴键盘。在这个键盘中，是否存在一个由 $W$ 个白键和 $B$ 个黑键组成的连续部分？

假设 $S$ 是由无限重复的字符串 wbwbwwbwbwbw 构成的字符串。

在 $S$ 中，是否存在一个由 $W$ 次出现的 w 和 $B$ 次出现的 b 组成的子串？

Solution

暴力把 $S$ 复制多次，然后 $n^2$ 找子串验证

应该还有更优的解法，只是串长实在太短，怎么写都行

Code

#include <bits/stdc++.h>
using namespace std;
int main() {
    int W, B; cin >> W >> B;
    string s, p = "wbwbwwbwbwbw";
    while (s.size() < 2000) s += p;
    int n = s.size(); s = " " + s; 
    vector<int> sumb(n + 1), sumw(n + 1);
    for (int i = 1; i <= n; i++) {
        sumb[i] = sumb[i - 1] + (s[i] == 'b');
        sumw[i] = sumw[i - 1] + (s[i] == 'w');
    }
    for (int i = 1; i <= n; i++)
        for (int j = i; j <= n; j++) {
            int nw = sumw[j] - sumw[i - 1], nb = sumb[j] - sumb[i - 1];
            if (W == nw && B == nb) {
                cout << "Yes" << endl;
                return 0;
            }
        }
    cout << "No" << endl;
    return 0;
}

C - Σ

Question

给你一个长度为 $N$ 的正整数序列 $A$ 和一个正整数 $K$

求在 $1$ 与 $K$ 之间，未出现在序列 $A$ 中的整数之和

Solution

先算 $1\sim K$ 中所有数的和，然后把在 $A$ 中的减去

注意 $A$ 中的 $A_i$ 可能不在 $1\sim K$ 这个范围内

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, k; cin >> n >> k;
    vector<int> a(n);
    for (int &x : a) cin >> x;
    sort(a.begin(), a.end());
    a.erase(unique(a.begin(), a.end()), a.end());
    int ans = k * (k + 1) / 2;
    for (int &x : a) {
        if (x <= k)
            ans -= x;
    }
    cout << ans << endl;
    return 0;
}

D - Gomamayo Sequence

Question

给你一个长度为 $N$ 的字符串 $S$ ，它由 0 和 1 组成

长度为 $N$ 的字符串 $T$ 由 0 和 1 组成，当且仅当它满足以下条件时，它是一个好字符串：

• 恰好有一个整数 $i$ 使得 $1\le i\le N-1$ 和 $T$ 的第 $i$ 个字母 和第 $(i+1)$ 个字符相同

对于每个 $i=1,2,\dots ,N$ ，您可以选择是否执行一次下面的操作：

• 如果 $S$ 的 $i$ 个字符是 0，则将其替换为 1，反之亦然。如果执行此操作，代价是 $Ci$

求使 $S$ 成为一个好字符串所需的最小总成本

Solution

考虑到有且仅有一个 $i$ ，满足 $T_i=T_{i+1}$，不妨假设 $T_i=T_{i+1}=1$，那么可知 $T_{i-1}=0,T_{i+2}=0$

$i$ 前面和 $i+1$ 后面都是 0101 交替的，我们就可以记录一个交错的前缀和

定义 $pre[i][0]$ 表示第 $i$ 个字母，前面都是 0101 交替的，且第 $i$ 个字母为 0 花费的最小代价，$pre[i][1]$ 表示第 $i$ 个字母，前面都是 0101 交替的，且第 $i$ 个字母为 1 花费的最小代价

同理，$suf[i][0]$ 表示第 $i$ 个字母，后面都是 0101 交替的，且第 $i$ 个字母为 0 花费的最小代价

如何计算 $pre$ ？交错着刷前缀和就好了

for (int i = 1; i <= n; i++) {
    pre[i][0] = pre[i - 1][1] + c[i] * (s[i] != '0');
    pre[i][1] = pre[i - 1][0] + c[i] * (s[i] != '1');
}

最后，关于 $T_i=T_{i+1}$ 只有 $0$，$1$ 两种情况，分别枚举一次即可

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    string s; cin >> s; s = " " + s;
    vector<ll> c(n + 1, 0);
    for (int i = 1; i <= n; i++)
        cin >> c[i];
    
    vector<vector<ll> > pre(n + 2 , vector<ll>(2, 0)); auto lst = pre;
    for (int i = 1; i <= n; i++) {
        pre[i][0] = pre[i - 1][1] + c[i] * (s[i] != '0');
        pre[i][1] = pre[i - 1][0] + c[i] * (s[i] != '1');
    }
    for (int i = n; i > 0; i--) {
        lst[i][0] = lst[i + 1][1] + c[i] * (s[i] != '0');
        lst[i][1] = lst[i + 1][0] + c[i] * (s[i] != '1');
    }

    ll ans = INF;

    //00
    for (int i = 1; i < n; i++) {
        ll now = c[i] * (s[i] != '0') + c[i + 1] * (s[i + 1] != '0');
        now += pre[i - 1][1] + lst[i + 2][1];
        ans = min(ans, now);
    }
    //11
    for (int i = 1; i < n; i++) {
        ll now = c[i] * (s[i] != '1') + c[i + 1] * (s[i + 1] != '1');
        now += pre[i - 1][0] + lst[i + 2][0];
        ans = min(ans, now);
    }
    cout << ans << '\n';
    return 0;
}

E - Paint

Question

有一个行数为 $H$ 列数为 $W$ 的网格。初始时，所有单元格都涂有颜色 $0$

您将按照 $i=1,2,\dots ,M$ 的顺序执行以下操作。

• 如果是 $T_i=1$ ，则使用颜色 $X_i$ 重新绘制 $A_i$ 行中的所有单元格。

• 如果是 $T_i=2$ ，则使用颜色 $X_i$ 重新绘制 $A_i$ 列中的所有单元格

完成所有操作后，针对网格中存在的每种颜色 $i$ ，找出被涂上颜色 $i$ 的单元格数量

Solution

显然，最后一次刷在墙上的颜色肯定存在，第二次如果和第一次方向不同，那么中间会有一个格子是第一次刷的颜色

按照这个想法，我们用 map 记录有多少行被刷了颜色，以及有多少列刷了颜色

倒叙处理，这一行/列 在这一次刷中保留了多少颜色，取决与有多少 列/行 还没有刷过

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> pii;
signed main() {
    freopen ("E.in","r",stdin);
    ios::sync_with_stdio(0); cin.tie(0);
    int H, W, N; cin >> H >> W >> N;
    vector<int> A(N + H), X(N + H), T(N + H); 
    N = N + H;
    for (int i = 0; i < H; i++) {
        T[i] = 1; A[i] = i + 1; X[i] = 0;
    }
    for (int i = H; i < N; i++)
        cin >> T[i] >> A[i] >> X[i];
    map<int,pii> col, row;
    for (int i = N - 1; i>= 0; i--) {
        if (T[i] == 1) {
            if (row.count(A[i])) continue;
            row[A[i]] = {W - col.size(), X[i]};
        }
        else {
            if (col.count(A[i])) continue;
            col[A[i]] = {H - row.size(), X[i]};
        }
    }
    map<int,int> mp;
    for (auto &r : row) {
        int num = r.second.first, c = r.second.second;
        if (!mp.count(c))
            mp[c] = 0;
        mp[c] += num; 
    }
    for (auto &r : col) {
        int num = r.second.first, c = r.second.second;
        if (!mp.count(c))
            mp[c] = 0;
        mp[c] += num; 
    }

    int ans = 0;
    for (auto &x : mp) 
        ans += x.second != 0;
    cout << ans << '\n';
    for (auto &x : mp) {
        if (x.second == 0) continue;
        cout << x.first << " " << x.second << '\n';
    }
    return 0;
}

F - SSttrriinngg in StringString

Question

对于长度为 $n$ 的字符串 $X$

• 让 $f(X,k)$ 表示重复 $k$ 次字符串 $X$ 得到的字符串
• $g(X,k)$ 表示依次重复 $k$ 次第一个字符、第二个字符、 $\dots$ 、 $X$ 的 $n$ 个字符得到的字符串

给你一个正整数 $N$ 和字符串 $S$ 和 $T$ 。求最大的非负整数 $k$ ，使得 $g(T,k)$ 是 $f(S,N)$ 的子序列

注意，根据定义， $g(T,0)$ 总是 $f(S,N)$ 的子序列

Solution

答案满足单调性，也就是说，如果 $g(T,k)$ 是 $f(S,N)$ 的子序列的话，对于所有的 $k^{\prime }\le k$ ，$g(T,k^{\prime })$ 也是 $f(S,N)$ 的子序列

所以我们二分最后的答案 $k$，考虑如何 check

提前预处理出 $S$ 字符出现的次数 以及 每个字符的第 $i$ 次出现的位置

记录此时枚举 $g(S,N)$ 的第 $iter$ 个字母

对于 $T$ 上的每个字母，都需要重复 $k$ 次，那么看需要多少整块的 $S$ 以及最后一块 $S$ 上的几个字母

按照题意模拟即可

Code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1ll << 60;

int main() {
    ll n;
    string S, T;
    cin >> n >> S >> T;
    int s = S.size(), t = T.size();
    vector<vector<int> > pos(26);
    for (int i = 0; i < s * 2; i++) 
        pos[S[i % s] - 'a'].push_back(i);
    vector<vector<int> >  pre(s + 1, vector<int>(26));
    for (int i = 0; i < s; i++) {
        pre[i + 1] = pre[i];
        pre[i + 1][S[i] - 'a']++;
    }
    vector<int> cnt(26, 0);
    for (int i = 0; i < s; i++)
        cnt[S[i] - 'a']++;
    ll le = 0, ri = INF;
    auto check = [&] (ll x) -> bool {
        ll iter = 0; // 表示s的长度
        for (int i = 0; i < t; i++) {
            int c = T[i] - 'a';
            if (cnt[c] == 0) return false;
            ll r = (x - 1) % cnt[c] + 1;
            ll q = (x - r) / cnt[c];
            if (q > INF / s) return false;
            iter += q * s;
            int nx = pos[c][pre[iter % s][c] + r - 1]; // 从iter % s开始的第r个c 的位置
            iter += nx - iter % s + 1;
            if (iter > n * s) return false;
        }
        return true;
    };

    while (le + 1 < ri) {
        ll mid = (le + ri) >> 1;
        if (check(mid)) le = mid;
        else ri = mid;
    }
    cout << le << endl;
    return 0;
}

G - Alone

Question

给你一个整数序列 $A$ 。

求满足以下条件的整数对 $(L,R)$ 的个数：

• $1\le L\le R\le N$
• 有一个数字在 $A_L,A_{L+1},\dots ,A_R$ 中恰好出现一次。更确切地说，有一个整数 $x$ 恰好有一个整数 $i$ 满足 $A_i=x$ 和 $L\le i\le R$

Solution

对于一个 $i$，提前预处理出 $pre[i]$ 和 $nxt[i]$，分别表示与 $a[i]$ 相同的前一个和后一个出现的位置

显然，一个区间的左端点可以在 $(pre[i],i]$ ，一个区间的右端点可以是 $[i,nxt[i])$

例如 2 2 1 2 1 ，当 $i=3,a[i]=1$

那么此时的 $pre[i]=0,nxt[i]=5$

$(1,3),(1,4),(2,3),(2,4),(3,3),(3,4)$ 都是合法的区间

对于一个 $i$ 可以生成这么多区间，显然最后的答案是对每个 $i$ 找区间，然后去重

关键是如何去重？ 我们发现一个 $i$ 生成的区间都是连续的，也就是说，如果把二元组看成二维平面上的一个坐标，那么一个 $i$ 生成的区间对应的是二维平面上的一个矩形

而矩形的左下角是 $(pre[i]+1,i)$ 右上角是 $(i,nxt[i]-1)$

显然，这个问题就转化为二维平面上 $n$ 个矩形的交集面积

利用扫描线算法就可以解决

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct Segment_Tree {
    int n;
    vector<int> sum, tag;
    Segment_Tree (int n) {
        this->n = n;
        tag.assign(n << 4, 0);
        sum.assign(n << 4, 0);
    }


    void update (int x, int l, int r, int ql, int qr, int val) {
        if (ql <= l && r <= qr) {
            tag[x] += val;
            if (tag[x]) sum[x] = r - l + 1;
            else sum[x] = sum[x << 1] + sum[x << 1 | 1];
            return ;
        }
        int mid = (l + r) >> 1;
        if (ql <= mid) update(x << 1, l, mid, ql, qr, val);
        if (qr > mid) update(x << 1 | 1, mid + 1, r, ql, qr, val);
        if (!tag[x]) sum[x] = sum[x << 1] + sum[x << 1 | 1];
    }

};

struct Line {
    int l, r, x, op;
    Line (int l, int r, int x, int op) : l(l), r(r), x(x), op(op) {}
    bool operator < (const Line &rhs) {
        if (x == rhs.x) return op < rhs.op;
        return x < rhs.x;
    }
};

int main() {
    freopen ("G.in", "r", stdin);
    int n; cin >> n;
    vector<int> a(n + 1);

    for (int i = 1; i <= n; i++)
        cin >> a[i];

    vector<int> pre(n + 1, 0), nxt(n + 1, n + 1), pos(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        pre[i] = pos[a[i]];
        pos[a[i]] = i;
    }
    pos.assign(n + 1, n + 1);
    for (int i = n; i; i--) {
        nxt[i] = pos[a[i]];
        pos[a[i]] = i;
    }
    
    vector<Line> lines;
    for (int i = 1; i <= n; i++) {
        lines.emplace_back(i, nxt[i] - 1, pre[i], 1);
        lines.emplace_back(i, nxt[i] - 1, i, -1);
    }
    
    Segment_Tree T(n);
    ll ans = 0;
    sort(lines.begin(), lines.end());
    for (int i = 0; i < lines.size() - 1; i++) {
        T.update(1, 1, n, lines[i].l, lines[i].r, lines[i].op);
        ans += 1ll * T.sum[1] * (lines[i + 1].x - lines[i].x);
    }
    cout << ans << endl;
    return 0;
}